Current data compression methods of compressing data by a dictionary-based method are derived from Abraham Lempel and Jacob Ziv, "A Universal Algorithm for Sequential Data Compression", IEEE Transaction on Information Theory (1977).
This method is generally called a Lempel-Ziv encoding slide dictionary method or LZ77 method.
The LZ77 method is introduced in, e.g., Seiji Munakata, "Ziv-Lempel Data Compression Method", Information Processing, Vol. 26, No. 1 (1985).
The LZ77 algorithm is a method of segmenting data to be encoded into a stream having a maximum matching length from an arbitrary position of a past data stream, and encoding the segmented stream as a copy of the past stream.
More specifically, as shown in FIG. 3, the LZ77 algorithm uses a moving window storing encoded input data and a prefetch buffer storing data to be encoded, and collates all partial sequences of a data sequence in the moving window with those in the prefetch buffer to obtain a matching partial sequence having a maximum length in the moving window.
To designate a partial sequence having a maximum length in the moving window, a combination of "the start position of a partial sequence having a maximum length", "a matching length", and "a next symbol which cancels matching" are encoded.
An encoded data sequence in the prefetch buffer is moved to the moving window, and a new data sequence corresponding to the encoded data sequence is input to the prefetch buffer.
The same processing is repeated to decompose data into partial sequences and encode the partial sequences.
Many improvements of this basic data compression technique have been proposed.
For example, there is an LZSS encoding method of setting a flag for identifying whether data is an encoded code or raw data and when the encoded data is longer than the raw data, encoding the raw data (T. C. Bell, "Better OPM/L Text Compression", IEEE Transaction Commun., Vol. COM-34, No. 12, Dec. (1986)).
Another reference is M. Nelson, "Data Compression Handbook: Second Edition", Toppan (1996), ISBN4-8101-8605-9.
In resent years, OA systems (scanners, printers, digital copying machines, and the like) are becoming popular, and higher speeds and higher resolutions are required.
These systems must process large-amount image data at a high speed, so that they must reduce the processing data amount by compressing data at a high speed and high compression ratio.
The conventional data compression technique includes standard methods such as MMR and JBIG. However, MMR tends to decrease the compression ratio for a fine image.
JBIG, which attains almost the highest compression ratio, basically processes data in units of pixels, is limited in an increase in speed, and thus cannot be employed in high-speed systems.
The above dictionary-based compression method basically processes data in units of bytes, can attain a much higher speed than JBIG, can keep the compression ratio for a fine image in comparison with MMR, and is suitable for high-speed, high-resolution OA systems.
In encoding, however, a conventional LZ77-based data compression apparatus must compare a data sequence to be encoded with data sequences starting from all positions in the moving window in order to obtain a matching partial data sequence having a maximum length in the moving window.
More specifically, as shown in FIG. 3, a data sequence to be encoded is compared with a data sequence starting from the position of offset 1 in the moving window, a data sequence starting from the position of offset 2, . . . , and a data sequence starting from the position of offset n (n is the size of the moving window), thereby finding an offset having a maximum matching length.
Hardware which implements this at a high speed is disclosed in U.S. Pat. No. 5,003,307.
As shown in FIG. 4, this hardware implements a moving window having a moving window size of n by n shift registers SR1 to SRn, and parallel-processes n comparisons using n comparators CMP1 to CMPn.
This method can advantageously process one data by one clock, but requires comparators equal in number to the moving window size and becomes difficult to realize for a larger moving window size.
For example, for a moving window size of 2 kB, this conventional method requires 2 k comparators.